插入排序法(insertion sort)介紹

「想像你在玩撲克牌，並且需要對手上的排牌由大而小進行排序，你會怎麼排?」

假設手上的牌由左到右分別如下:
2,4,7,5,10

為了排序，我們先判斷了

• 2 < 4 不用動
• 4 < 7 不用動
• 7 > 5 需調換

則我們會將5與7對調，得到2,4,5,7,10

• 5 < 7
• 7 < 10

得知所有結果均正確。

而這個過程中，我們會先判斷手上的牌的"排序情況"，並在出現不符合排序情況的數字時，將其"插入"(insert)到正確的位置。這種在排序撲克牌時腦袋所做出的排序方式以程式的演算法實現就稱為"插入排序法(insertion sort)"而我們也可以把上述比較的過程想像為我們依序拿到發牌者發的牌

拿到2時:整體序列不用動，目前的數列裡有:2
拿到4時:因為2 < 4，將4放到2的右邊，目前的數列裡有:2,4
拿到7時:因為4 < 7，將7放到4的右邊，目前的數列裡有:2,4,7
拿到5時:因為5 < 7，將5放在4和7間，目前的數列裡有:2,4,5,7
拿到10時::因為7 < 10，將10放到7的右邊，目前的數列裡只有:2,4,5,7,10，排序完成!

Pseudocode(虛擬碼)展示

第一部分:什麼是pseudocode?

首先這裡提到一個新的名詞"pseudocode(虛擬碼)"，這是演算法在呈現程式時常用的方式。虛擬碼並不是一種真實的程式語言，但他能以較高層級(接近自然語言)的方式來呈現一個程式的骨幹與流程。而我們也能透過虛擬碼的呈現來套到不同的程式語言上執行與測試。

第二部分:什麼是BigO和Time Complexity(時間複雜度)

在程式執行時我們常會運用兩項標準"time/space complexity"(時間/空間複雜度)來描述程式的執行效率。時間就是代表他的執行時間的量質；而空間就是指他的register(暫存器)使用量，也就是程式所需要的空間的量質。

而因為程式中的時間與空間不可能以像是"秒"或是"GB"作為計算標準，因為同樣的程式在不同的資料量下都會有不同的佔用量。為了統一程式間比較的準則，我們運用一個符號O()(念作Big O)，來代表最糟情況的複雜度(通常我們會以最糟情況來估計他的效能)。而Big O通常會寫作如:O(n)、O(n^2)、O(logn)等方式，裡面的n就代表了"多少次"的時間。

常見排序： 1(常數) < log n < n < n log n < n^2 < 2^n < n! (越右邊代表Big O越大等同程式須執行越久)

而次數的計算方式如迴圈的層數計算或是程式的邏輯判斷都可以大略估計出他的Big O值。

第三部分:insertion sort的pseudocode

for j = 2 to A.length do //A為此堆資料的陣列
    data = A[j] //data為要插入的資料
    i = j-1
    while i > 0 and A[i] > data do
        A[i+1] = A[i]; //若新插入的資料比較小，就把已經排序好的原資料向後移
        i = i-1; //繼續向前檢查，直到新插入資料比較大為止
    end while
    A[j+1] = data; //最後將空下來的位置讓給新插入的資料
end for

可以看到我們運用i,j兩變數去實現將data(待插入資料)與原本的數列順序進行比較，以while迴圈帶領data填入正確的位置。

在insertion的部分(while迴圈)，我們得知是n次(因為最糟的情況每個數字都需要牌續，比較共i+1次)
而在整體insertion sort的部分因為再加上資料總共有n比，time complexity就為O(n^2)

那我們明後天會繼續介紹其他的sort，那就明天見囉(´▽`ʃ♡ƪ)

參考資料:

1. https://kopu.chat/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8Finsertion-sort/
2. https://zh.wikipedia.org/zh-tw/%E4%BC%AA%E4%BB%A3%E7%A0%81